public class Test36 {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean dp[][] = new boolean[n][n];
        int len = 1;
        int left = 0;
        for(int i = n - 1;i >= 0;i--) {
            for(int j = i;j < n;j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = j - i < 2 ? true : dp[i + 1][j - 1];
                }
                if(dp[i][j] && j - i + 1> len) {
                    len = j - i + 1;
                    left = i;
                }
            }
        }
        return s.substring(left,len + left);
    }
    //     int n = s.length();
    //     String[] dp = new String[n];
    //     dp[0] = "" + s.charAt(0);
    //     int maxLen = 0;
    //     int index = 0;
    //     for(int i = 1;i < n;i++) {
    //         for(int j = 0;j < i;j++) {
    //             if(isPalindrome(j,i,s)) {
    //                 dp[i] = s.substring(j,i + 1);
    //                 if(maxLen < (i - j + 1)) {
    //                     maxLen = i - j + 1;
    //                     index = i;
    //                 }
    //                 break;
    //             }
    //         }
    //     }
    //     return dp[index];
    // }
    // public Boolean isPalindrome(int left,int right,String str) {
    //     String s = str.substring(left,right + 1);
    //     int k = (right - left + 1) / 2;
    //     int l = 0;
    //     int r = s.length() - 1;
    //     while (k > 0) {
    //         if(s.charAt(l) == s.charAt(r)) {
    //             l++;
    //             r--;
    //         }
    //         else return false;
    //         k--;
    //     }
    //     return true;
    // }
}

